package bszt.xiecheng;

import java.util.Scanner;

public class Code03 {

    /**
     * 问题描述
     * LYA有一个长度为n的数组，她想知道对于给定的若干个区间，区间内所有元素的乘积模6的值是多少。你能帮帮她吗？
     * <p></p>
     * 输入格式
     * 第一行输入两个正整数n和q，分别表示数组的长度以及询问的次数
     * 第二行输入n个正整数a_i，表示数组中的元素
     * 接下来的q行，每行输入两个正整数l和r，表示一次询问的区间为第l个数到第r个数（包括第l和第r个数）
     * <p></p>
     * 输出格式
     * 输出共q行，第i行表示第i次询问的结果
     */

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int q = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        for (int i = 0; i < q; i++) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            System.out.println(getMul(arr, l - 1, r - 1));
        }
    }

    public static int getMul(int[] arr, int l, int r) {
        int mul = 1;
        for (int i = l; i <= r; i++) {
            mul = (mul * arr[i]) % 6;
        }
        return mul;
    }
}
